package com.captain.leetcode.二维数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2021/7/30 16:05
 */
public class 插入区间57 {
    public static void main(String[] args) {

        int[][] arr = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        for (int[] ints : new 插入区间57().insert(null, new int[]{4, 8})) {
            System.out.println(Arrays.toString(ints));
        }

    }

    public int[][] insert(int[][] intervals, int[] newInterval) {

//        [1][3]   [4][7]
//        [2][6]
//        [8][10]
//        [15][18]
        if (intervals == null) {
            int[][] res = new int[1][];
            res[0] = newInterval;
            return res;
        }

        int[][] arr = new int[intervals.length + 1][];
        System.arraycopy(intervals, 0, arr, 0, intervals.length);
        arr[intervals.length] = newInterval;
        //排序
        Arrays.sort(arr, Comparator.comparingInt(o -> o[0]));
        int start = arr[0][0];
        //一行一行的遍历进行比较
        int len = arr.length;
        List<int[]> res = new ArrayList<>();
        for (int i = 1; i < len; i++) {
            int pre = arr[i - 1][1];
            int next = arr[i][0];
            if (pre < next) {
                res.add(new int[]{start, arr[i - 1][1]});
                start = arr[i][0];
            } else {
                arr[i][1] = Math.max(arr[i - 1][1], arr[i][1]);
            }
        }
        res.add(new int[]{start, arr[arr.length - 1][1]});
        return res.toArray(new int[res.size()][]);
    }
}
